package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.5 MB, 在所有 Go 提交中击败了68.64%的用户
 */
func nextPermutation(nums []int)  {

	k := len(nums) - 1
	for k - 1 >= 0 && nums[k - 1] >= nums[k] { k-- }

	if k == 0 {  // 说明当前序列是最大值, 返回最小值即可
		reverse(&nums, 0, len(nums) - 1)
	} else {
		t := k
		for t < len(nums) && nums[t] > nums[k - 1] { t++ }
		swap(&nums, k - 1, t - 1)
		reverse(&nums, k, len(nums) - 1)
	}
}

// 翻转 nums[i...j]的部分
func reverse(nums *[]int, i int, j int) {

	for i < j {
		(*nums)[i], (*nums)[j] = (*nums)[j], (*nums)[i]
		i, j = i + 1, j - 1
	}
}

// 交换nums[i]和nums[j]
func swap(nums *[]int, i int, j int) {
	(*nums)[i], (*nums)[j] = (*nums)[j], (*nums)[i]
}

func main() {

	nums := []int{1, 2, 3}
	nextPermutation(nums)
	fmt.Println(nums)
}
